package 剑指offer;

import leetcode.editor.cn.MergeListNode;
import 抽象数据类型.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-21
 */
public class 两个链表生成相加链表 {
    public static void main(String[] args) {
        ListNode l1 = null;
        ListNode l2 = null;
        l1 = MergeListNode.proList(new int[]{9, 3, 7}, 0, l1);
        l2 = null;
        ListNode listNode = addInList1(l1, l2);
        System.out.println(listNode);

    }

    //1.通过数组
    public static ListNode addInList(ListNode head1, ListNode head2) {
        // write code here
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        while (head1 != null) {
            list1.add(0, head1.val);
            head1 = head1.next;
        }
        while (head2 != null) {
            list2.add(0, head2.val);
            head2 = head2.next;
        }
        int index = 0;
        List<Integer> sum = new ArrayList<>();
        int cal = 0;
        while (index < list1.size() || index < list2.size()) {
            if (index >= list1.size()) {
                list1.add(0);
            }
            if (index >= list2.size()) {
                list2.add(0);
            }
            int temp = list1.get(index) + list2.get(index) + cal;
            sum.add(temp % 10);
            cal = temp / 10;
            index++;
        }
        if (cal != 0) {
            sum.add(cal);
        } else {
            index = index - 1;
        }
        ListNode newNode = new ListNode(Integer.MAX_VALUE);
        ListNode temp = newNode;
        while (index >= 0) {
            temp.next = new ListNode(sum.get(index));
            temp = temp.next;
            index--;
        }
        return newNode.next;
    }

    //2.通过递归
    public static void overNum(ListNode head1, ListNode head2, AtomicInteger val) {
        if (head1 == null && head2 == null) {
            return;
        }
        overNum(head1.next, head2.next, val);
        int sum = (head1 == null ? 0 : head1.val) + (head2 == null ? 0 : head2.val) + val.get();
        if (sum / 10 > 0) {
            val.set(1);
        } else {
            val.set(0);
        }
        head1.val = sum % 10;
    }

    public static ListNode addInList1(ListNode head1, ListNode head2) {
        ListNode point1 = head1;
        ListNode point2 = head2;
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        int length1 = 0;
        int length2 = 0;
        while (point1.next != null) {
            point1 = point1.next;
            length1++;
        }
        while (point2.next != null) {
            point2 = point2.next;
            length2++;
        }
        int gap = Math.abs(length1 - length2);
        ListNode node = new ListNode(0);
        ListNode temp = node;
        while (gap != 0) {
            gap--;
            temp.next= new ListNode(0);
            temp = temp.next;
        }
        if (length1 != length2) {
            if (length1 > length2) {
                temp.next = head2;
                head2=node.next;
            } else {
                temp.next = head1;
                head1=node.next;
            }
        }
        AtomicInteger add = new AtomicInteger(0);
        overNum(head1, head2, add);
        if (add.get() == 1) {
            ListNode listNode = new ListNode(1);
            listNode.next=head1;
            return listNode;
        }
        return head1;
    }
}
